package com.foxzzz.dynamic.programming;

import com.alibaba.fastjson.JSON;

import java.util.List;

public class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1) return triangle.get(0).get(0);
        int[] dp=new int[triangle.get(triangle.size()-1).size()];
        dp[0]=triangle.get(0).get(0);
        int result=Integer.MAX_VALUE;
        for (int i = 1; i < triangle.size(); i++) {
            for (int j=triangle.get(i).size()-1;j>-1; j--) {
                int min=0;
                if(j-1<0)
                    min=dp[j];
                else if(j==triangle.get(i).size()-1)
                    min=dp[j-1];
                else
                    min=Math.min(dp[j],dp[j-1]);
                dp[j]=min+triangle.get(i).get(j);
                if(i==triangle.size()-1)
                    result=dp[j]<result?dp[j]:result;
            }

        }


        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Solution120().minimumTotal((List<List<Integer>>) JSON.parse("[[-10]]")));
    }
}
